#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
#
# @param pRootOfTree TreeNode类
# @return TreeNode类
#
class TreeNode:
    def __init__(self,val):
        self.val = val
        self.right = None
        self.left = None

def constructTree(nums):
    if not nums:
        return None
    maxVal = float("-inf")
    index = 0
    for i in range(len(nums)):
        if nums[i] > maxVal:
            maxVal = nums[i]
            index = i

    root = TreeNode(maxVal)
    root.left = constructTree(nums[:index])
    root.right = constructTree(nums[index+1:])
    return root

class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return None
        minRes = []

        def midTraverse(root):
            if not root:
                return None
            midTraverse(root.left)
            minRes.append(root)
            midTraverse(root.right)

        midTraverse(pRootOfTree)
        # 主要是利用v和minRes两种表示法来改变双向链表的指针
        for k, v in enumerate(minRes[0:len(minRes) - 1]):
            v.right = minRes[k + 1]
            minRes[k + 1].left = v
        print(minRes)
        return minRes[0]
class Solution1:
    def levelOrder(self , root):
        def do(root ,level):
            if root == None:
                return
            else:
                if len(self.treelist) < level:
                    self.treelist.append([])
                self.treelist[level-1].append(root.val)
                if root.left != None:
                    do(root.left, level+1)
                if root.right != None:
                    do(root.right, level+1)
        # write code here
        self.treelist = []
        do(root,1)
        return self.treelist

if __name__=="__main__":
    nums = [3,2,1,6,0,5,10,8,9,7,13,11]
    root = constructTree(nums)
    # s = Solution1()
    # print(s.levelOrder(root))
    s = Solution()
    s.Convert(root)